package com.dhu.graph.utils;

import java.util.Arrays;
import java.util.Iterator;

/**
 * @Author ：snow
 * @Date ：Created in 2020-04-22
 * @Description：
 * @Modified By：
 * @Version:
 */
public class ArrayQueue<Item> implements Iterable<Item>{
    private Item[] arr;
    private int head;
    private int tail;
    private int cap;
    private static final int DEFAULT_CAPACITY = 16;
    private int N;

    public ArrayQueue(int cap){
        this.arr = (Item[])new Object[cap];
    }
    public ArrayQueue(){
        this.arr =(Item[]) new Object[DEFAULT_CAPACITY];
        this.cap = DEFAULT_CAPACITY;
    }
    public int size(){
        return this.N;
    }

    /**
     * 入队
     * @param item
     */
    public void enqueue(Item item){
        arr[tail++] = item;
        N++;
        if(N >= 0.75 * cap) resize(cap * 2);
    }
    public Item dequeue(){
        if(!isEmpty()){
            Item ret = arr[head];
            arr[head++] = null;
            N--;
            return ret;
        }
        return null;
    }
    private void resize(int newCap){
        Item[] newArr = (Item[])new Object[newCap];
        Item[] temp = Arrays.copyOfRange(arr, head, tail - 1);
        for(int i = 0; i < temp.length; i++){
            newArr[i] = temp[i];
        }
        this.head = 0;
        this.tail = N;
    }
    public  boolean isEmpty(){
        return this.head == this.tail;
    }


    @Override
    public Iterator<Item> iterator() {
       return new Itr();
    }
    private class Itr implements Iterator<Item>{
        private final Item[] elements = ArrayQueue.this.arr;
        private int cursor = -1;
        int count = ArrayQueue.this.N;
        @Override
        public boolean hasNext() {
            return cursor < count;
        }

        @Override
        public Item next() {
            return elements[++cursor];
        }

    }
}
